/*!
 * \file vEBTree.h
 * \brief A van Emde Boas tree data structure.
 *
 * \date Jun 18, 2012
 * \author correa
 */

#ifndef VEBTREE_H_
#define VEBTREE_H_

#include <stdlib.h>
#include <stdio.h>
#include "BitTools.h"
#include "OrderedSet.h"

template<typename T> class vEBTreeFactory;


/*! \class vEBTree
 * \brief A OrderedSet implement as a static van Emde Boas tree to store a set of elements
 * from a fixed universe of natural numbers.
 *
 * This class implements a ordered set in which the elements are natural numbers from a fixed
 * interval, start from 0. The order used in this class is the natural notion of bigger than.
 *
 * This class is specially designed to provide fast enumeration of the set or the entire universe.
 * For this purpose, this class stores one bit for each element of the universe. If the bit of an element
 * equals 1, then this element is in the set. Otherwise, this element is in the complement.
 *
 * Each level of the tree is a vEBTree itself in order to make the implementation of the classes
 * that inherit from vEBTree easier. This class has almost all the public methods implemented, a
 * child class only need to implement the protected ones.
 *
 * \sa http://en.wikipedia.org/wiki/Van_Emde_Boas_tree
 *
 * \tparam T the type of a word
 */
template <typename T>
class vEBTree : public OrderedSet<long>{

public:
	long n;//!< number of elements in the universe.

	int	logn;//!< logarithmic of the number of elements of the universe.

	int height;//!< number of levels of the tree.

	int logw;//!< logarithmic of the size, in bytes, of a word.

	int logb;//!< logarithmic of the size, in bits, of a word.

	long maskb;//!< mask used to obtain remainder of division by logb.

	int word_size;//!< number of bits of a word.

	vEBTree<T>** levels;//!<< up levels of the tree.

	long* bitvector;//!< to be returned by toArray().

	/*!
	 * \brief A constructor used internally to create other trees.
	 */
	vEBTree() : bitvector(NULL) {};

	/*!
	 * \brief The base constructor.
	 *
	 * It is to be used in the children classes to make same calculation about the size of the type T.
	 *
	 * \param size the size of the universe indexed by the structure.
	 */
	vEBTree(int size);

	/*!
	 * \brief The index of the node contain the specified element in the structure.
	 *
	 * This value is usually given by the floor of the specified element divided by the size of a word.
	 * But it depends on the implementation. For instance, if we wish to use 2 bits to index each element
	 * of the universe, the value would be the floor of the element divided by 2 times the size of a word.
	 *
	 * If i is a value bigger than the size of the universe a invalid index will be return, but it does
	 * not index any valid node.
	 *
	 * \param i the specified element.
	 *
	 * \return The index of the node of the specified element in the structure.
	 *
	 */
	virtual long wordIdx(long i)=0;

	/*!
	 *
	 * \brief The index of the specified element in a node(word).
	 *
	 * This value is usually given by the remainder of the specified element divided by the size of a word.
	 * But ir depends on the implementation.
	 *
	 * \param i the specified element.
	 *
	 * \return The index of the specified element in a node(word).
	 *
	 */
	virtual long inWordIdx(long i) = 0;

	/*!
	 * \brief The smallest element in the set, that is bigger than i and belong to the same node of i.
	 *
	 * This method has to be implemented in each child class, and depends on the number of bits used to
	 * index each element of the universe.
	 *
	 * \param i the specified element.
	 *
	 * \return The smallest element in the set, that is bigger than i and belong to the same node of i.
	 */
	virtual long nextSetInWord(long i) = 0;

	/*!
	 * \brief The smallest element in the complement, that is bigger than i and belong to the same node of i.
	 *
	 * This method has to be implemented in each child class, and depends on the number of bits used to
	 * index each element of the universe.
	 *
	 * \param i the specified element
	 *
	 * \return The smallest element in the complement, that is bigger than i and belong to the same node of i.
	 */
	virtual long nextComplInWord(long i) = 0;

	/*!
	 * \brief Count the number of elements in the set on a specified node.
	 *
	 * This method has to be implemented in each child class, and depends on the number of bits used to
	 * index each element of the universe.
	 *
	 * \param i the specified node.
	 *
	 * \return the number of elements in the set on the node index by i.
	 */
	virtual long countSetInWord(long i) = 0;

	/*!
	 * \brief Count the number of elements in the complement on a specified node.
	 *
	 * This method has to be implemented in each child class, and depends on the number of bits used to
	 * index each element of the universe.
	 *
	 * \param i the specified node.
	 *
	 * \return the number of elements in the complement on the node index by i.
	 */
	virtual long countComplInWord(long i) = 0;

	/*!
	 * \brief The smallest element bigger than i that is in the set.
	 *
	 * This method has to be implemented in each child class, and it difers of the method nextSetElement()
	 * because it does not use the others levels in the tree. It is a search only in the level.
	 *
	 * \param i the specified element.
	 *
	 * \return the smallest element bigger than i that is in the set, if there is no such element, it will
	 * return same value bigger than the cardinality of the universe.
	 */
	virtual long nextSetElementInLevel(long i) = 0;

	/*!
	 * \brief The smallest element bigger than i that is in the complement.
	 *
	 * This method has to be implemented in each child class, and it difers of the method nextSetElement()
	 * because it does not use the others levels in the tree. It is a search only in the level.
	 *
	 * \param i the specified element.
	 *
	 * \return the smallest element bigger than i that is in the complement, if there is no such element, it will
	 * return same value bigger than the cardinality of the universe.
	 */
	virtual long nextComplElementInLevel(long i) = 0;

	/*!
	 * \brief The node in the index i of the leaf level of the tree.
	 *
	 * This method should be implemented in each child class. It is to be used used for the
	 * methods in the father class as a way to retrieve nodes in each level of the tree, that
	 * is a vEBTree of only one level.
	 *
	 * If the index i is not a valid one, a error will occur
	 *
	 * \param i the index of the node to be retrieve.
	 *
	 * \return the i-th node in the tree
	 */
	virtual T treeNode(long i) = 0;

	/*!
	 * \brief Replaces the node in the position i by the specified node
	 *
	 *	Replace the node in the position index by i, by the node newnode and update the
	 *	structure to keep the meaning of the upper levels.
	 *
	 *	If the index is not a validy one an erro will occur.
	 *
	 * \param i the position to be change
	 *
	 * \param newnode the specified node
	 *
	 * \return true if the operation sucessed and false otherwise
	 */
	virtual bool setNode(long i, T newnode) = 0;

	/*!
	 * \brief Replaces the node in the position i by the specified node without
	 * make any update in the structure.
	 *
	 *	Replace the node in the position index by i, by the node newnode and update the
	 *	structure to keep the meaning of the upper levels.
	 *
	 *	If the index is not a validy one an erro will occur.
	 *
	 * \param i the position to be change
	 *
	 * \param newnode the specified node
	 *
	 * \return true if the operation sucessed and false otherwise
	 */
	virtual bool setNodeInLevel(long i, T newnode) = 0;

	/*!
	 * \brief Retrive the first element in the i-th node of the tree
	 *
	 * This method is used in a node to look for the first bit in the node
	 * that is one. It will be usully implemented with a builtin function.
	 *
	 * If the index of the node is not a valid one, a error will occur.
	 *
	 * \param i the index of the node
	 *
	 * \return the position of the first bit 0 in the i-th node.
	 */
	virtual long firstSetInWord(long i) = 0;

	/*!
	 * \brief Retrive the first element in the i-th node of the tree that belongs to the complement
	 *
	 * This method is used in a node to look for the first bit in the node
	 * that is zero. It will be usully implemented with a builtin function.
	 *
	 * If the index of the node is not a valid one, a error will occur.
	 *
	 * \param i the index of the node
	 *
	 * \return the position of the first bit 0 in the i-th node.
	 */
	virtual long firstComplInWord(long i) = 0;

	/*!
	 * \brief Add the specified element to the set, without update the information in the other levels.
	 *
	 * This method is necessary for speed issues. In order to make the implementation quicker, we can
	 * change the information of only one level of the tree.
	 *
	 * If the element is not a member of the universe a erro will occur.
	 *
	 * This method should not be used by any child class. As it does not make any update in the structure,
	 * same information in the levels may be wrong and the methods can behaive
	 *
	 * \param i the specified element
	 */
	virtual void toSetInLevel(long i) = 0;

	/*!
	 * \brief Remove the specified element to the set, without update the information in the other levels.
	 *
	 * This method is necessary for speed issues. In order to make the implementation quicker, we can
	 * change the information of only one level of the tree.
	 *
	 * If the element is not a member of the universe a erro will occur.
	 *
	 * This method should not be used by any child class. As it does not make any update in the structure,
	 * same information in the levels may be wrong and the methods can behaive
	 *
	 * \param i the specified element.
	 */
	virtual void toComplInLevel(long i) = 0;

	/*!
	 * \brief Add all the elements of the universe to the set, without update the information in the other levels.
	 *
	 * This method is necessary for speed issues. in order to make the implementation quicker, we can
	 * change the information of only one level of the tree.
	 *
	 * This method should not be used by any child class. As it does not make any update in the structure,
	 * same information in the levels may be wrong and the methods can behaive
	 *
	 */
	virtual void allToSetInLevel() = 0;

	/*!
	 * \brief Remove all the elements of the universe to the set, without update the information in the other levels.
	 *
	 * This method is necessary for speed issues. in order to make the implementation quicker, we can
	 * change the information of only one level of the tree.
	 *
	 * This method should not be used by any child class. As it does not make any update in the structure,
	 * same information in the levels may be wrong and the methods can behaive
	 *
	 */
	virtual void allToComplInLevel() = 0;


public:

	/*! \class Iterator
	 * \brief A generic iterator on the set of elements.
	 *
	 * The elements are enumerated in an increasing order.
	 *
	 * An object of this class keeps the state of an enumeration. This means that various enumerations can
	 * be performed simultaneously provided that each of them is associated with a different iterator.
	 *
	 * The path from the root of the tree until last element enumerated is composed by nodes of the vEBTree.
	 * A binary search in this path using min and max information of subtrees allows a \f$O(\log \log n)\f$
	 * time complexity for each access.
	 *
	 */
	class Iterator : public OrderedSet<long>::Iterator{
		friend class vEBTree;

	protected:
		int ht;//!< a copy of the target instance of vEBTree<T>::height.

		vEBTree<T>*	t;//!< the enclosing vEBTree<T>, which gives access to vEBTree<T>::treeNode method.

		long current;//<! the current item in the enumeration

		long idx;//!< index of the current node in the last level.

		long word_size;//!< the size in bits of a word

		long size;//!< the size of the vEBTree that is being enumerate, its a simple copy of the value t->size().

		/*!
		 * \brief A constructor for a Iterator over a specified vEBTree.
		 *
		 * Create a Iterator to look up a specified vEBTree. The Iterator enumerate
		 * all the elements in the set represented by the object passed as parameter.
		 *
		 * \param t the specified tree.
		 */
		Iterator(vEBTree<T> * t);


	public:
		/*!
		 * \brief The destructor.
		 */
		virtual ~Iterator();

		/*!
		 * \brief Start enumeration.
		 *
		 * Initailize all the variables and start a enumeration of the elements in the set.
		 *
		 * The variables idx and slide are set to zero and the initial word is set to be
		 * the first non null word.
		 */
		virtual void start();


		/*!
		 * \brief Restart enumeration.
		 *
		 * Restart the enumeration. It will lost all the current state and it will start over the
		 * enumeration.
		 *
		 * Usually it is a simple call to start().
		 *
		 * \see start()
		 *
		 */
		virtual void restart();

		/*!
		 * \brief Restart enumeration from a specified element.
		 *
		 * Restart the enumeration. it will lost all the current state and it will
		 * start over from the smalest element in the set that is bigger or equal
		 * than the specified element.
		 *
		 * If the specified element is not a element of the universe a error will
		 * occur.
		 *
		 * \param the specified element
		 */
		virtual void restartFrom(long i);

		/*!
		 * \brief Determine if still there is a element in the set not enumerated yet.
		 *
		 * This method determine if there is a element in the set not enumerate yet. It look
		 * in all the leaf level of the tree using the information of the other levels.
		 *
		 * We start the search in the word of the least enumerated element. If it has other bit 1
		 * we return this value. If not we look in the upper level for the next non null word and so
		 * go on untill the top level where we make a serial search.
		 *
		 * \return true if there is a element not enumerated yet, and false otherwise.
		 */
		virtual bool hasNext();

		/*!
		 * \brief Index of the next element in the set according to the current enumeration.
		 *
		 * The next element in the current enumeration. The order is the natural order between the natural
		 * numbers.
		 *
		 * \return the next element, if exists one; otherwise, a value greater or equal to the size of the universe.
		 */
		virtual long next();
	};

	/*! \class Iterator
	 * \brief A filtered iterator on the set of elements.
	 *
	 * The elements are enumerated in an increasing order, but only the ones that belong
	 * to the filter as well.
	 *
	 * An object of this class keeps the state of an enumeration. This means that various enumerations can
	 * be performed simultaneously provided that each of them is associated with a different iterator.
	 *
	 * The path from the root of the tree until last element enumerated is composed by nodes of the vEBTree.
	 * A binary search in this path using min and max information of subtrees allows a \f$O(\log \log n)\f$
	 * time complexity for each access.
	 *
	 */
	class FilterIterator : public OrderedSet<long>::Iterator{
		friend class vEBTree;

	protected:
		vEBTree<T>*	t;//!< the enclosing vEBTree<T>, which gives access to vEBTree<T>::treeNode method.

		OrderedSet<long>* filter;//!< the filter to enumeration

		long current;//<! the current item in the enumeration

		long idx;//!< index of the current node in the last level.

		long word_size;//!< the size in bits of a word

		long size;//!< the size of the vEBTree that is being enumerate, its a simple copy of the value t->size().

		/*!
		 * \brief A constructor for a Iterator over a specified vEBTree.
		 *
		 * Create a Iterator to look up a specified vEBTree. The Iterator enumerate
		 * all the elements in the set represented by the object passed as parameter.
		 *
		 * \param t the specified tree.
		 *
		 * \param filter the filter to the correspondent enumeration
		 */
		FilterIterator(vEBTree<T> * t, OrderedSet<long>* filter);

	public:
		/*!
		 * \brief The destructor.
		 */
		virtual ~FilterIterator();

		/*!
		 * \brief Start enumeration.
		 *
		 * Initailize all the variables and start a enumeration of the elements in the set.
		 *
		 * The variables idx and slide are set to zero and the initial word is set to be
		 * the first non null word.
		 */
		virtual void start();


		/*!
		 * \brief Restart enumeration.
		 *
		 * Restart the enumeration. It will lost all the current state and it will start over the
		 * enumeration.
		 *
		 * Usually it is a simple call to start().
		 *
		 * \see start()
		 *
		 */
		virtual void restart();

		/*!
		 * \brief Restart enumeration from a specified element.
		 *
		 * Restart the enumeration. it will lost all the current state and it will
		 * start over from the smalest element in the set that is bigger or equal
		 * than the specified element.
		 *
		 * If the specified element is not a element of the universe a error will
		 * occur.
		 *
		 * \param the specified element
		 */
		virtual void restartFrom(long i);

		/*!
		 * \brief Determine if still there is a element in the set and in the filter not enumerated yet.
		 *
		 * This method determine if there is a element in the set and in the filter not enumerate yet. It look
		 * in all the leaf level of the tree using the information of the other levels.
		 *
		 * We start the search in the word of the least enumerated element. If it has other bit 1
		 * we return this value. If not we look in the upper level for the next non null word and so
		 * go on untill the top level where we make a serial search.
		 *
		 * \return true if there is a element not enumerated yet that belongs to the set and the filter
		 * , and false otherwise.
		 */
		virtual bool hasNext();

		/*!
		 * \brief Index of the next element in the set according to the current enumeration.
		 *
		 * The next element in the current enumeration. The order is the natural order between the natural
		 * numbers.
		 *
		 * \return the next element, if exists one; otherwise, a value greater or equal to the size of the universe.
		 */
		virtual long next();
	};


	/*!
	 * \brief Adds a new level to the tree.
	 *
	 * This new level is created just above the current smallest level of the tree. The implementation
	 * of vEBTree used in this level is determined by the specified factory.
	 * If the current smallest level is 0 (the tree has all level already), then no new level is created.
	 *
	 * Realize that this method allow us to build a tree with different data structure in each level,
	 * and different relations between levels as well.
	 *
	 * \param f a factory for the implementation of the new level.
	 *
	 * \return the level added. If less than zero, then no level has been added.
	 */
	virtual bool newLevel(OrderedSetFactory<long> * f);

	/*!
	 * \brief A destructor.
	 *
	 * All data used are deleted and memory space are cleaned.
	 */
	virtual ~vEBTree();

	/*!
	 * \brief Create a copy of this object.
	 *
	 * A concrete implementation of this class must override this method in order to perform the copy of the
	 * data structure.
	 *
	 * \return a copy of this object.
	 */
	virtual OrderedSet<long>* clone() = 0;

	/*!
	 * \brief Start a new iterator for the set represented by this object.
	 *
	 * The state of the returned iterator is reset to the beginning of the enumeration.
	 *
	 * \return a iterator over the set represented by this object.
	 */
	virtual OrderedSet<long>::Iterator* newSetIterator(){
		return new Iterator(this);
	}

	/*!
	 * \brief Start a new iterator for the set represented by this object with a filter.
	 *
	 * The state of the returned iterator is reset to the beginning of the enumeration.
	 * The enumeration is filtered by the set passed as parameter.
	 *
	 * \param filter a filter to eliminate same elements of the enumeration.
	 *
	 * \return a iterator over the set represented by this object.
	 */
	virtual OrderedSet<long>::Iterator* newSetIterator(OrderedSet<long>* filter){
		return new FilterIterator(this, filter);
	}

	/*!
	 * \brief Start a new iterator for the complement of the set represented by this object.
	 *
	 * The state of the returned iterator is reset to the beginning of the enumeration.
	 *
	 * \return a iterator over the complement of the set represented by this object.
	 */
	virtual OrderedSet<long>::Iterator* newComplIterator(){
		//TODO fazer iterador para o complemento
		vEBTree<T>* copy = (vEBTree<T>*)clone();
		copy->setComplement();
		return new Iterator(copy);
	}

	/*!
	 * \brief Start a new iterator for the complement represented by this object with a filter.
	 *
	 * The state of the returned iterator is reset to the beginning of the enumeration.
	 * The enumeration is filtered by the set passed as parameter.
	 *
	 * \param filter a filter to eliminate same elements of the enumeration.
	 *
	 * \return a iterator over the complement represented by this object.
	 */
	virtual OrderedSet<long>::Iterator* newComplIterator(OrderedSet<long>* filter){
		//TODO fazer iterador com filtro para o complemento
		vEBTree<T>* copy = (vEBTree<T>*)clone();
		copy->setComplement();
		return new FilterIterator(copy, filter);
	}

	/*!
	 * \brief Determine the next element in the set of the specified element.
	 *
	 * The smallest element of the universe which is in the set and is greater than the specified element (which is not
	 * required to be in the set).
	 *
	 * \param i the element from which this method determines the next element.
	 *
	 * \return the first element after the specified one in the set, if exists one; otherwise, a value greater or equal to the size of the universe.
	 */
	virtual long nextSetElement(long i);

	/*!
	 * \brief Determine the next element in the set, of the specified element.
	 *
	 * The smallest element of the universe which is in the set and is greater than the specified element (which is not
	 * required to be in the set).
	 *
	 * \param i the element from which this method determines the next element.
	 *
	 * \return the first element after the specified one in the set, if exists one; otherwise, a value greater or equal to the size of the universe.
	 */
	virtual long nextComplElement(long i);

	/*!
	 * \brief Add the specified element to the set, removing it from the complement.
	 *
	 * As a result of this operation, the specified element appears in an enumeration of the set. It depends
	 * of the implementation.
	 *
	 * This method is optional. If i is not in the universe a error will occur.
	 *
	 * \param i the element to add.
	 */
	virtual void toSet(long i) = 0;

	/*!
	 * \brief Add the specified element to the complement, removing it from the set.
	 *
	 * As a result of this operation, the specified element disappears in an enumeration of the set. It depends
	 * of the implementation.
	 *
	 * This method is optional. If i is not in the universe a error will occur.
	 *
	 * \param i the element to add.
	 */
	virtual void toCompl(long i) = 0;

	/*!
	 * \brief Flip the status of the current element.
	 *
	 * If the current element is in the set, then it is removed from the set (and included in the complement). Otherwise,
	 * the current element is removed from the complement (and included in the set). The status of the current element
	 * changes for each invocation of this method (so, if it is applied twice for the same element, then its status after
	 * these invocation is the same as before them).
	 *
	 * If the current element is not valid, then an error may occur.
	 *
	 * \param i the specified element.
	 */
	virtual void flipElement(long i);

	/*!
	 * \brief Determines whether the specified element is in this set.
	 *
	 * If the specified element is not in the universe a error will occur. This method
	 * should be implement in the concrete class because it make use of a data structure
	 * to store the information about the set.
	 *
	 * \param i the specified element.
	 *
	 * \return true if  i is in the set, and false otherwise.
	 */
	virtual bool isInSet(long i) = 0;

	/*!
	 * \brief Determines whether the specified element is in this complement.
	 *
	 * If the specified element is in the universe a error will occur. This method
	 * should be implement in the concrete class because it make use of a data structure
	 * to store the information about the set.
	 *
	 * \param i the specified element.
	 *
	 * \return true if i is in the complement, and false otherwise.
	 */
	virtual bool isInCompl(long i) = 0;

	/*!
	 * \brief Returns an array containing all of the elements in this set in increasing order.
	 *
	 * At the discretion of the implementation, this object may maintain a reference to the returned array.
	 * This method acts as bridge between array-based and eVBTree-based APIs.
	 * The size of the vector is returned in the pointer size.
	 *
	 * \param size a pointer to store the number of elements in the set.
	 *
	 * \return an array containing all the elements in this vEBTree.
	 *
	 */
	virtual long* toArray(long* size) = 0;

	/*!
	 *  \brief The number of elements present in the universe.
	 *
	 *  This is the value passed as parameter to the constructor, it is important to notice that
	 *  this is not the real size of the tree, actually the real size of the tree is about \f$ 2size\f$.
	 *
	 *  \return the number of bits used to index all the elements of the universe.
	 */
	virtual long size();

	/*!
	 * \brief The number of nodes(words) used to index all the universe
	 *
	 * This method is dependent of the implementation. Usually, this number is the size of the universe times
	 * the number of bits used to index a single element and divided by the size of T.
	 *
	 * \return the number of node used to represent the whole universe.
	 */
	virtual long sizeInWord() = 0;

	/*!
	 * \brief Verify if the current set represeted by this object is empty
	 *
	 * For each node in the top level of the tree we test if it is a null word. Child
	 * classes must overwrite this method ih other to make this operation quicker.
	 *
	 * \return true if the set represented by the object is empty and false otherwise.
	 */
	virtual bool isEmpty();

	/*!
	 *  \brief Add all the elements of the universe to the set.
	 *
	 * The abstract class implement it with by simply call this same method in each level of the
	 * current tree. Each child should implement this method in a very fast way in order to make
	 * the function efficient.
	 */
	virtual void allToSet()=0;

	/*!
	 *  \brief Add all the elements of the universe to the complement.
	 *
	 * The abstract class implement it with by simply call this same method in each level of the
	 * current tree. Each child should implement this method in a very fast way in order to make
	 * the function efficient.
	 */
	virtual void allToCompl()=0;

	/*!
	 *  \brief The set operation of complement.
	 *
	 *  This operation overwrite the current object with the complement of the set represented by it.
	 *  More precisely, if i belongs to the set it is removed and if i do not belong it is added.
	 *
	 */
	virtual void setComplement();

	/*!
	 *  \brief The set operation of complement.
	 *
	 * This operation has the same semantic and restrictions of logicneg(), but do not overwrite the object with the
	 * result. A new vEBTree is used to store the result.
	 *
	 * The vEBTree used to store the result has to respect same restrictions:
	 * - should be empty, otherwise the result may change.
	 * - has to be a size equal to the current object at each level, it may not has all the levels
	 * presented in the current tree.
	 * If it is not the case a error will occur.
	 *
	 *  \param res a new vEBTree to store the complement of the set.
	 */
	virtual void setComplement(vEBTree<T> * res);

	/*!
	 *  \brief The set operation of complement.
	 *
	 * This operation has the same semantic and restrictions of logicneg(), but do not overwrite the object with the
	 * result. A new OrderedSet<long> is used to store the result.
	 *
	 *  \param res a new OrderedSet<long> to store the complement of the set.
	 */
	virtual void setComplement(OrderedSet<long>* res);

	/*!
	 *  \brief The set operation of union between the currents set represented by this object
	 *  and by v.
	 *
	 *  This operation overwrite the current object with the union between the current set and
	 *  the set represented by the vEBTree v.
	 *
	 *  More precisely, let be *A* the set represented by the current object and *B* the set represented
	 *  to v. For all  *i* in the universe
	 *  if \f$ i \in A \f$ or \f$ i \in B \f$ then *i* is added to *A*, otherwise is removed.
	 *
	 *  The vEBTree passed as parameter to the operation has to respect same restrictions:
	 *	- has to have the same size of the current one.
	 *	- has to have at least the same number of levels in the current one.
	 *	If it is not the case a error will occur.
	 *
	 *  It is important to notice that the valid of the operation depends on the order of
	 *  the operands. For example if a vEBTree of size 3 call this method for a vEBTree of
	 *  size 5 the method successed, but the converse failed.
	 *
	 *  \param v the set to be operated with the current one.
	 */
	virtual void setUnionSet(vEBTree<T> * v);

	/*!
	 *  \brief The set operation of symmetric difference between the currents sets represented by this object
	 *  and by v.
	 *
	 *  This operation overwrite the current object with the union between the current set and
	 *  the set represented by the vEBTree v.
	 *
	 *  More precisely, let be *A* the set represented by the current object and *B* the set represented
	 *  to v. For all  *i* in the universe
	 *  if \f$ i \in A \f$ e \f$ i \notin B \f$ or \f$ i \notin A \f$ e \f$ i \in B \f$  then *i* is added to *A*,
	 *  otherwise is removed.
	 *
	 *  The vEBTree passed as parameter to the operation has to respect same restrictions:
	 *	- has to have the same size of the current one.
	 *	- has to have at least the same number of levels in the current one.
	 *	If it is not the case a error will occur.
	 *
	 *  It is important to notice that the valid of the operation depends on the order of
	 *  the operands. For example if a vEBTree of size 3 call this method for a vEBTree of
	 *  size 5 the method successed, but the converse failed.
	 *
	 *  \param v the set to be operated with the current one.
	 */
	virtual void setDiffSimetricSet(vEBTree<T> * v);

	/*!
	 *  \brief The set operation of intersection  between the currents sets represented by this object
	 *  and by v.
	 *
	 *  This operation overwrite the current object with the union between the current set and
	 *  the set represented by the vEBTree v.
	 *
	 *  More precisely, let be *A* the set represented by the current object and *B* the set represented
	 *  to v. For all  *i* in the universe
	 *  if \f$ i \in A \f$ e \f$ i \in B \f$ then *i* is added to *A*, otherwise is removed.
	 *
	 *  The vEBTree passed as parameter to the operation has to respect same restrictions:
	 *	- has to have the same size of the current one.
	 *	- has to have at least the same number of levels in the current one.
	 *	If it is not the case a error will occur.
	 *
	 *  It is important to notice that the valid of the operation depends on the order of
	 *  the operands. For example if a vEBTree of size 3 call this method for a vEBTree of
	 *  size 5 the method successed, but the converse failed.
	 *
	 *  \param v the set to be operated with the current one.
	 */
	virtual void setIntersecSet(vEBTree<T> * v);

	/*!
	 *  \brief The set operation of union between the currents sets represented by this object and
	 *  by v; The result is stored in res.
	 *
	 * This operation has the same semantic and restrictions of logicor(), but do not overwrite the object with the
	 * result. A new vEBTree is used to store the result.
	 *
	 * The vEBTree used to store the result has to respect same restrictions:
	 * - should be empty, otherwise the result may change.
	 * - must have a size equal to the current object's at each level, but not necessarily has all the same number
	 * of levels.
	 * If it is not the case an error will occur.
	 *
	 *  \param v the set to be operated with the current one.
	 *  \param res a set to store the result of the operation.
	 *
	 */
	virtual void setUnionSet(vEBTree<T> * v, vEBTree<T> * res);

	/*!
	 *  \brief The set operation of symmetric difference between the currents sets represented by this object and
	 *  by v; The result is stored in res.
	 *
	 * This operation has the same semantic and restrictions of logicxor(), but do not overwrite the object with the
	 * result. A new vEBTree is used to store the result.
	 *
	 * The vEBTree used to store the result has to respect same restrictions:
	 * - should be empty, otherwise the result may change.
	 * - must have a size equal to the current object's at each level, but not necessarily has all the same number
	 * of levels.
	 * If it is not the case an error will occur.
	 *
	 *  \param v the set to be operated with the current one.
	 *  \param res a set to store the result of the operation.
	 *
	 */
	virtual void setDiffSimetricSet(vEBTree<T> * v, vEBTree<T> * res);

	/*!
	 *  \brief The set operation of intersection between the currents sets represented by this object and
	 *  by v; The result is stored in res.
	 *
	 * This operation has the same semantic and restrictions of logicand(), but do not overwrite the object with the
	 * result. A new vEBTree is used to store the result.
	 *
	 * The vEBTree used to store the result has to respect same restrictions:
	 * - should be empty, otherwise the result may change.
	 * - must have a size equal to the current object's at each level, but not necessarily has all the same number
	 * of levels.
	 * If it is not the case an error will occur.
	 *
	 *  \param v the set to be operated with the current one.
	 *  \param res a set to store the result of the operation.
	 *
	 */
	virtual void setIntersecSet(vEBTree<T> * v, vEBTree<T> * res);

	/*!
	 *  \brief The set operation of union between the complement set represented by this object and
	 *  the set represented by v.
	 *
	 *  This operation overwrite the current object with the union between the current set and
	 *  the set represented by the vEBTree v.
	 *
	 *  More precisely, let be *A* the set represented by the current object and *B* the set represented
	 *  to v. For all  *i* in the universe
	 *  if \f$ i \notin A \f$ or \f$ i \in B \f$ then *i* is added to *A*, otherwise is removed.
	 *
	 *  The vEBTree passed as parameter to the operation has to respect same restrictions:
	 *	- has to have the same size of the current one.
	 *	- has to have at least the same number of levels in the current one.
	 *	If it is not the case a error will occur.
	 *
	 *  It is important to notice that the valid of the operation depends on the order of
	 *  the operands. For example if a vEBTree of size 3 call this method for a vEBTree of
	 *  size 5 the method successed, but the converse failed.
	 *
	 *  \param v the set to be operated with the current one.
	 *
	 */
	virtual void complUnionSet(vEBTree<T> * v);

	/*!
	 *  \brief The set operation of intersection between the complement set represented by this object and
	 *  the set represented by v.
	 *
	 *  This operation overwrite the current object with the union between the current set and
	 *  the set represented by the vEBTree v.
	 *
	 *  More precisely, let be *A* the set represented by the current object and *B* the set represented
	 *  to v. For all  *i* in the universe
	 *  if \f$ i \notin A \f$ e \f$ i \in B \f$ then *i* is added to *A*, otherwise is removed.
	 *
	 *  The vEBTree passed as parameter to the operation has to respect same restrictions:
	 *	- has to have the same size of the current one.
	 *	- has to have at least the same number of levels in the current one.
	 *	If it is not the case a error will occur.
	 *
	 *  It is important to notice that the valid of the operation depends on the order of
	 *  the operands. For example if a vEBTree of size 3 call this method for a vEBTree of
	 *  size 5 the method successed, but the converse failed.
	 *
	 *  \param v the set to be operated with the current one.
	 *
	 */
	virtual void complIntersecSet(vEBTree<T> * v);

	/*!
	 *  \brief The set operation of union between the complement set represented by this object and
	 *  the set represented by v; The result is stored in res.
	 *
	 * This operation has the same semantic and restrictions of logicand(), but do not overwrite the object with the
	 * result. A new vEBTree is used to store the result.
	 *
	 * The vEBTree used to store the result has to respect same restrictions:
	 * - should be empty, otherwise the result may change.
	 * - must have a size equal to the current object's at each level, but not necessarily has all the same number
	 * of levels.
	 * If it is not the case an error will occur.
	 *
	 *  \param v the set to be operated with the current one.
	 *  \param res a set to store the result of the operation.
	 *
	 */
	virtual void complUnionSet(vEBTree<T> * v, vEBTree<T> * res);

	/*!
	 *  \brief The set operation of intersection between the complement set represented by this object and
	 *  the set represented by v; The result is stored in res.
	 *
	 * This operation has the same semantic and restrictions of logicand(), but do not overwrite the object with the
	 * result. A new vEBTree is used to store the result.
	 *
	 * The vEBTree used to store the result has to respect same restrictions:
	 * - should be empty, otherwise the result may change.
	 * - must have a size equal to the current object's at each level, but not necessarily has all the same number
	 * of levels.
	 * If it is not the case an error will occur.
	 *
	 *  \param v the set to be operated with the current one.
	 *  \param res a set to store the result of the operation.
	 *
	 */
	virtual void complIntersecSet(vEBTree<T> * v, vEBTree<T> * res);

	/*!
	 *  \brief The set operation of union between the current set represented by this object and
	 *  the complement of the set represented by v.
	 *
	 *  This operation overwrite the current object with the union between the current set and
	 *  the set represented by the vEBTree v.
	 *
	 *  More precisely, let be *A* the set represented by the current object and *B* the set represented
	 *  to v. For all  *i* in the universe
	 *  if \f$ i \in A \f$ or \f$ i \notin B \f$ then *i* is added to *A*, otherwise is removed.
	 *
	 *  The vEBTree passed as parameter to the operation has to respect same restrictions:
	 *	- has to have the same size of the current one.
	 *	- has to have at least the same number of levels in the current one.
	 *	If it is not the case a error will occur.
	 *
	 *  It is important to notice that the valid of the operation depends on the order of
	 *  the operands. For example if a vEBTree of size 3 call this method for a vEBTree of
	 *  size 5 the method successed, but the converse failed.
	 *
	 *  \param v the set to be operated with the current one.
	 *
	 */
	virtual void setUnionCompl(vEBTree<T> * v);

	/*!
	 *  \brief The set operation of intersection between the current set represented by this object and
	 *  the complement of the set represented by v.
	 *
	 *  This operation overwrite the current object with the union between the current set and
	 *  the set represented by the vEBTree v.
	 *
	 *  More precisely, let be *A* the set represented by the current object and *B* the set represented
	 *  to v. For all  *i* in the universe
	 *  if \f$ i \in A \f$ e \f$ i \notin B \f$ then *i* is added to *A*, otherwise is removed.
	 *
	 *  The vEBTree passed as parameter to the operation has to respect same restrictions:
	 *	- has to have the same size of the current one.
	 *	- has to have at least the same number of levels in the current one.
	 *	If it is not the case a error will occur.
	 *
	 *  It is important to notice that the valid of the operation depends on the order of
	 *  the operands. For example if a vEBTree of size 3 call this method for a vEBTree of
	 *  size 5 the method successed, but the converse failed.
	 *
	 *  \param v the set to be operated with the current one.
	 *
	 */
	virtual void setIntersecCompl(vEBTree<T> * v);

	/*!
	 *  \brief The set operation of union between the current set represented by this object and
	 *  the complement of the set represented by v; The result is stored in res.
	 *
	 * This operation has the same semantic and restrictions of logicorneg(), but do not overwrite the object with the
	 * result. A new vEBTree is used to store the result.
	 *
	 * The vEBTree used to store the result has to respect same restrictions:
	 * - should be empty, otherwise the result may change.
	 * - must have a size equal to the current object's at each level, but not necessarily has all the same number
	 * of levels.
	 * If it is not the case an error will occur.
	 *
	 *  \param v the set to be operated with the current one.
	 *  \param res a set to store the result of the operation.
	 *
	 */
	virtual void setUnionCompl(vEBTree<T> * v, vEBTree<T> * res);

	/*!
	 *  \brief The set operation of intersection between the current set represented by this object and
	 *  the complement of the set represented by v. The result is stored in res.
	 *
	 * This operation has the same semantic and restrictions of logicandneg(), but do not overwrite the object with the
	 * result. A new vEBTree is used to store the result.
	 *
	 * The vEBTree used to store the result has to respect same restrictions:
	 * - should be empty, otherwise the result may change.
	 * - must have a size equal to the current object's at each level, but not necessarily has all the same number
	 * of levels.
	 * If it is not the case an error will occur.
	 *
	 *  \param v the set to be operated with the current one.
	 *  \param res a set to store the result of the operation.
	 *
	 */
	virtual void setIntersecCompl(vEBTree<T> * v, vEBTree<T> * res);

	/*!
	 *  \brief The set operation of union between the complement set represented by this object and
	 *  the complement set represented by v.
	 *
	 *  This operation overwrite the current object with the union between the current set and
	 *  the set represented by the vEBTree v.
	 *
	 *  More precisely, let be *A* the set represented by the current object and *B* the set represented
	 *  to v. For all  *i* in the universe
	 *  if \f$ i \notin A \f$ ou \f$ i \notin B \f$ then *i* is added to *A*, otherwise is removed.
	 *
	 *  The vEBTree passed as parameter to the operation has to respect same restrictions:
	 *	- has to have the same size of the current one.
	 *	- has to have at least the same number of levels in the current one.
	 *	If it is not the case a error will occur.
	 *
	 *  It is important to notice that the valid of the operation depends on the order of
	 *  the operands. For example if a vEBTree of size 3 call this method for a vEBTree of
	 *  size 5 the method successed, but the converse failed.
	 *
	 *  \param v the set to be operated with the current one.
	 *
	 */
	virtual void complUnionCompl(vEBTree<T> * v);

	/*!
	 *  \brief The set operation of intersection between the complement set represented by this object and
	 *  the complement set represented by v.
	 *
	 *  This operation overwrite the current object with the union between the current set and
	 *  the set represented by the vEBTree v.
	 *
	 *  More precisely, let be *A* the set represented by the current object and *B* the set represented
	 *  to v. For all  *i* in the universe
	 *  if \f$ i \notin A \f$ e \f$ i \notin B \f$ then *i* is added to *A*, otherwise is removed.
	 *
	 *  The vEBTree passed as parameter to the operation has to respect same restrictions:
	 *	- has to have the same size of the current one.
	 *	- has to have at least the same number of levels in the current one.
	 *	If it is not the case a error will occur.
	 *
	 *  It is important to notice that the valid of the operation depends on the order of
	 *  the operands. For example if a vEBTree of size 3 call this method for a vEBTree of
	 *  size 5 the method successed, but the converse failed.
	 *
	 *  \param v the set to be operated with the current one.
	 *
	 */
	virtual void complIntersecCompl(vEBTree<T> * v);

	/*!
	 *  \brief The set operation of union between the complement set represented by this object and
	 *  the complement set represented by v; The result is stored in res.
	 *
	 * This operation has the same semantic and restrictions of logicnor(), but do not overwrite the object with the
	 * result. A new vEBTree is used to store the result.
	 *
	 * The vEBTree used to store the result has to respect same restrictions:
	 * - should be empty, otherwise the result may change.
	 * - must have a size equal to the current object's at each level, but not necessarily has all the same number
	 * of levels.
	 * If it is not the case an error will occur.
	 *
	 *  \param v the set to be operated with the current one.
	 *  \param res a set to store the result of the operation.
	 *
	 */
	virtual void complUnionCompl(vEBTree<T> * v, vEBTree<T> * res);

	/*!
	 *  \brief The set operation of intersection between the complement set represented by this object and
	 *  the complement set represented by v; The result is stored in res.
	 *
	 * This operation has the same semantic and restrictions of logicnand(), but do not overwrite the object with the
	 * result. A new vEBTree is used to store the result.
	 *
	 * The vEBTree used to store the result has to respect same restrictions:
	 * - should be empty, otherwise the result may change.
	 * - must have a size equal to the current object's at each level, but not necessarily has all the same number
	 * of levels.
	 * If it is not the case an error will occur.
	 *
	 *  \param v the set to be operated with the current one.
	 *  \param res a set to store the result of the operation.
	 *
	 */
	virtual void complIntersecCompl(vEBTree<T> * v, vEBTree<T> * res);

	/*!
	 *  \brief Look for the first element of the universe in the set.
	 *
	 *  It determines the first element in the set, if the set is empty it will
	 *  return -1.
	 *
	 *  The abstract class implements this method by make a search start from the root
	 *  of the tree and look at level for the least element in the set. If the child class can make
	 *  this faster it has to overwrite this method.
	 *
	 *  \return The smallest number in the set, if the set is empty it will return -1.
	 */
	virtual long firstInSet();

	/*!
	 *  \brief Look for the first element of the universe in the complement.
	 *
	 *  It determines the first element in the complement, if the set is all the universe it will
	 *  return -1.
	 *
	 *  The abstract class implements this method by make a search start from the root
	 *  of the tree and look at level for the least element in the complement. If the child class can make
	 *  this faster it has to overwrite this method.
	 *
	 *  \sa builtinLeast()
	 *
	 *  \return the smallest number in the complement if the set is all the universe
	 *  it will return -1.
	 */
	virtual long firstInCompl();

	/*!
	 *  \brief The numbers of elements in the current set represented by this object.
	 *
	 *  The abstract class implements this method using the static iterator to look at each non
	 *  empty word in the leaf level of the tree and uses a builtin function to efficiently count
	 *  the number of bits 1 in the word. The Filter specified to the iterator is the
	 *  object itself.
	 *
	 *  \sa biultinLeast()
	 *
	 *  \return The size of the current set.
	 */
	virtual long cardOfSet();

	/*!
	 *  \brief The numbers of elements of the current complement set represented by this object.
     *
	 *  The abstract class implements this method using the static iterator to look at each non
	 *  empty word in the leaf level of the tree and uses a builtin function to efficiently count
	 *  the number of bits 1 in the word. The Filter specified to the iterator is the
	 *  result of logicneg() applied to the current object.
	 *
	 *  \return The size of the current complement set.
	 */
	virtual long cardOfCompl();

	//DEBUG
	void show();

};

template<typename T>
vEBTree<T>::~vEBTree(){
	delete bitvector;
}

template<typename T>
vEBTree<T>::vEBTree( int size){
	//initialize the variables
	logn = inline_ceillog(size, 1);
	logw = inline_ceillog(sizeof(T), 1);
	logb = logw + 3;
	maskb = ~(-1L << logb);
	word_size = 1LL << logb;
	n = size;
	height = 1;
	levels = NULL;
	bitvector = NULL;
}


template<typename T>
inline bool vEBTree<T>::newLevel(OrderedSetFactory<long> * f){
	//copy the current vetor of trees
	height++;
	vEBTree<T>** newlevels = new vEBTree<T>*[height];
	for(long i = 0; i < height-1;i++){
		newlevels[i] = levels[i];
	}

	//create the new level
	int sz = levels[height-2]->size();
	sz = (sz >> logb)<<logb == sz? (sz >> logb): (sz >> logb) + 1;
	levels[height-1] = (vEBTree<T>*)f->newOrderedSet(sz);

	//update the new level
	for(long i = 0; i < levels[height-2]->sizeInWord(); i++){
		if(levels[height - 2]->treeNode(i) != 0)levels[height-1]->toSet(i);
	}
	return false;
}

template<typename T>
inline long vEBTree<T>::nextSetElement(long i){

	//determine the index and position of the element
	long index = wordIdx(i);
	long inword = nextSetInWord(i);
	vEBTree<T>* current = levels[0];
	long j = 1;

	//look in each level for the next
	while(j < height && inword == -1){
		current = levels[j++];
		index++;
		if(index < current->size()){
			inword = current->nextSetInWord(index);
			index = current->wordIdx(index);
		}else return n+1;

	}

	//if it not found a bit 1, look at the root vector for the next bit 1
	if(inword == -1){
		inword = current->nextSetElementInLevel((index+1) << logb);
		index = 0;
	}

	// go down in the tree looking for the bit 1
	if(inword != -1){
		for(j = j - 2 ; j >= 0; j--){
			current = levels[j];
			index = (index << logb) + inword;
			if(index < current->sizeInWord())inword = current->firstSetInWord(index);
			else return n+1;
		}
		return inword + (index << logb);
	}

	return n + 1;

}


template<typename T>
inline long vEBTree<T>::nextComplElement(long i){

	//determine the index and position of the element
	long index = wordIdx(i);
	long inword = nextComplInWord(i);
	vEBTree<T>* current = NULL;
	long j = 1;

	//look in each level for the next
	while(j < height && inword == -1){
		current = levels[j++];
		index++;
		if(index < current->size()){
			inword = current->nextComplInWord(index);
			index = current->wordIdx(index);
		}else return n+1;

	}

	//if it not found a bit 1, look at the root vector for the next bit 1
	if(inword == -1 && current != NULL){
		inword = current->nextComplElementInLevel((index << logb )+1);
		index = 0;
	}

	// go down in the tree looking for the bit 1
	if(inword != -1){
		for(j = j - 2 ; j >= 0; j--){
			current = levels[j];
			index = (index << logb) + inword;
			if(index < current->sizeInWord())inword = current->firstComplInWord(index);
			else return n+1;
		}
		return inword + (index << logb);
	}

	return n + 1;
}


template<typename T>
inline void vEBTree<T>::flipElement(long i){
	if(isInSet(i))toCompl(i);
	else toSet(i);
}


template<typename T>
inline long vEBTree<T>::size(){
	return n;
}


template<typename T>
inline void vEBTree<T>::setComplement(){
	long sz = sizeInWord();
	for(long i = 0; i < sz; i++){
		setNode(i, ~treeNode(i));
	}
}

template<typename T>
inline void vEBTree<T>::setComplement(vEBTree<T> * res){
	long sz = sizeInWord();
	for(long i = 0; i < sz; i++){
		res->setNode(i, ~treeNode(i));
	}
}

template<typename T>
inline void vEBTree<T>::setComplement(OrderedSet<long>* res){
	res = clone();
	res->setComplement();
}

template<typename T>
inline void vEBTree<T>::setDiffSimetricSet(vEBTree<T> * v){
	long sz = sizeInWord();
	for(long i = 0; i < sz; i++){
		setNode(i, v->treeNode(i)^treeNode(i));
	}
}

template<typename T>
inline void vEBTree<T>::setUnionSet(vEBTree<T> * v){
	int nextv=0, sz = sizeInWord();
	if(height > 1){
		//enumerate all the non empty words in v
		vEBTree<T>* up = v->levels[1];
		nextv = up->nextSetElement(nextv);
		while(nextv < sz ){
			// if the index is valid, make the operation
			setNode(nextv, treeNode(nextv)| v->treeNode(nextv));
			nextv++;
			nextv = up->nextSetElement(nextv);
		}
	}else{
		//in the case that v has no upper level
		for(long i = 0; i < sz; i++){
			setNodeInLevel(i, treeNode(i)| v->treeNode(i));
		}
	}
}

template<typename T>
inline void vEBTree<T>::setIntersecSet(vEBTree<T> * v){
	int nextu=0, sz = sizeInWord();
	if(height > 1){
		vEBTree<T>* up = levels[1];
		nextu = up->nextSetElement(nextu);
		while(nextu < sz ){
			//enumerate all the non empty words in the current object
			setNode(nextu, treeNode(nextu)& v->treeNode(nextu));
			nextu++;
			nextu = up->nextSetElement(nextu);
		}
	}else{
		//in the case that v has no upper level
		for(long i = 0; i < sz; i++){
			setNodeInLevel(i, treeNode(i) & v->treeNode(i));
		}
	}
}

template<typename T>
inline void vEBTree<T>::setUnionSet(vEBTree<T> * v, vEBTree<T> * res){
	int nextv=0, nextu=0, min = 0, sz = sizeInWord();
	if(height > 1){
		//look for the non null word in both trees
		vEBTree<T>* aup = levels[1];
		vEBTree<T>* bup = v->levels[1];
		nextu = aup->nextSetElement(min);
		nextv = bup->levels[1]->nextSetElement(min);
		min = nextu < nextv ? nextu : nextv;

		while(min < sz ){
			//operate the non null words
			res->setNode(min, treeNode(min)| v->treeNode(min));
			min++;
			nextu = aup->nextSetElement(min);
			nextv = bup->nextSetElement(min);
			min = nextu < nextv ? nextu : nextv;
		}
	}
	else{
		//in the case that the object has no upper level
		for(long i = 0; i < sz; i++){
			res->setNode(i, treeNode(i)| v->treeNode(i));
		}
	}
}

template<typename T>
inline void vEBTree<T>::setDiffSimetricSet(vEBTree<T> * v, vEBTree<T> * res){
	long sz = sizeInWord();
	for(long i = 0; i < sz; i++){
		res->setNode(i, v->treeNode(i)^treeNode(i));
	}
}

template<typename T>
inline void vEBTree<T>::setIntersecSet(vEBTree<T> * v, vEBTree<T> * res){
	int nextv=0, nextu=0, max = 0, sz = sizeInWord();
	if(height > 1){
		//look for the non null words in both trees
		vEBTree<T>* aup = levels[1];
		vEBTree<T>* bup = v->levels[1];
		nextu = aup->nextSetElement(max);
		nextv = bup->levels[1]->nextSetElement(max);
		max = nextu < nextv ? nextv : nextu;

		//operate the non null words and update the upper levels of the tree
		while(max < sz ){
			while(nextu != nextv){
				if(nextu < nextv)nextu = aup->nextSetElement(max);
				else nextv = bup->nextSetElement(max);
			}
			if(max < sz)res->setNode(max, treeNode(max)& v->treeNode(max));
			max = nextu+1;
		}
	}
	else{
		//in the case that the object has no upper level
		for(long i = 0; i < sz; i++){
			res->setNode(i, treeNode(i)& v->treeNode(i));
		}
	}
}

template<typename T>
inline void vEBTree<T>::complUnionSet(vEBTree<T> * v){
	long sz = sizeInWord();
	for(long i = 0; i < sz; i++){
		setNode(i, v->treeNode(i) | ~treeNode(i));
	}
}

template<typename T>
inline void vEBTree<T>::complIntersecSet(vEBTree<T> * v){
	long sz = sizeInWord();
	for(long i = 0; i < sz; i++){
		setNode(i, v->treeNode(i) & ~treeNode(i));
	}
}

template<typename T>
inline void vEBTree<T>::complUnionSet(vEBTree<T> * v, vEBTree<T> * res){
	long sz = sizeInWord();
	for(long i = 0; i < sz; i++){
		res->setNode(i, v->treeNode(i)|~treeNode(i));
	}
}

template<typename T>
inline void vEBTree<T>::complIntersecSet(vEBTree<T> * v, vEBTree<T> * res){
	long sz = sizeInWord();
	for(long i = 0; i < sz; i++){
		res->setNode(i, v->treeNode(i)& ~treeNode(i));
	}
}

template<typename T>
inline void vEBTree<T>::setUnionCompl(vEBTree<T> * v){
	long sz = sizeInWord();
	for(long i = 0; i < sz; i++){
		setNode(i, ~v->treeNode(i) | treeNode(i));
	}
}

template<typename T>
inline void vEBTree<T>::setIntersecCompl(vEBTree<T> * v){
	long sz = sizeInWord();
	for(long i = 0; i < sz; i++){
		setNode(i, ~v->treeNode(i) & treeNode(i));
	}
}

template<typename T>
inline void vEBTree<T>::setUnionCompl(vEBTree<T> * v, vEBTree<T> * res){
	long sz = sizeInWord();
	for(long i = 0; i < sz; i++){
		res->setNode(i, ~v->treeNode(i)|treeNode(i));
	}
}

template<typename T>
inline void vEBTree<T>::setIntersecCompl(vEBTree<T> * v, vEBTree<T> * res){
	long sz = sizeInWord();
	for(long i = 0; i < sz; i++){
		res->setNode(i, ~v->treeNode(i)&treeNode(i));
	}
}

template<typename T>
inline void vEBTree<T>::complUnionCompl(vEBTree<T> * v){
	long sz = sizeInWord();
	for(long i = 0; i < sz; i++){
		setNode(i, ~v->treeNode(i) | ~treeNode(i));
	}
}

template<typename T>
inline void vEBTree<T>::complIntersecCompl(vEBTree<T> * v){
	long sz = sizeInWord();
	for(long i = 0; i < sz; i++){
		setNode(i, ~v->treeNode(i) & ~treeNode(i));
	}
}

template<typename T>
inline void vEBTree<T>::complUnionCompl(vEBTree<T> * v, vEBTree<T> * res){
	long sz = sizeInWord();
	for(long i = 0; i < sz; i++){
		res->setNode(i, ~v->treeNode(i)|~treeNode(i));
	}
}

template<typename T>
inline void vEBTree<T>::complIntersecCompl(vEBTree<T> * v, vEBTree<T> * res){
	long sz = sizeInWord();
	for(long i = 0; i < sz; i++){
		res->setNode(i, ~v->treeNode(i)&~treeNode(i));
	}
}

template<typename T>
inline long vEBTree<T>::firstInSet(){
	return nextSetElement(0);
}

template<typename T>
inline long vEBTree<T>::firstInCompl(){
	return nextComplElement(0);
}


template<typename T>
inline long vEBTree<T>::cardOfSet(){
	long counter = 0;
	long next = 0;
	long sz = sizeInWord();
	vEBTree<T>* up = levels[1];
	if(height > 1){
		//enumerate all the upper vector
		next = up->nextSetElement(next);
		while(next < (sz - 1)){
			counter += countSetInWord(next);
			next++;
			next = up->nextSetElement(next);
		}
		counter += countSetInWord(sz-1);
	}else{
		//in the case that the object has no upper level
		for(next = 0; next < sz; next++){
			counter += countSetInWord(next);
		}
	}
	return counter;
}

template<typename T>
inline long vEBTree<T>::cardOfCompl(){
	return n - cardOfSet();
}

template<typename T>
vEBTree<T>::Iterator::Iterator(vEBTree<T>* t){
	this->t = t;
	word_size = t->word_size;
	size = t->size();
	current = 0;
}

template<typename T>
vEBTree<T>::Iterator::~Iterator(){
}

template<typename T>
inline void vEBTree<T>::Iterator::start(){
	//initialize the variables
	current = t->nextSetElement(0);
	if(current >= size) current = -1;
}

template<typename T>
inline void vEBTree<T>::Iterator::restart(){
	start();
}

template<typename T>
inline void vEBTree<T>::Iterator::restartFrom(long i){
	current = t->nextSetElement(i);
	if(current >= size) current = -1;
}

template<typename T>
inline bool vEBTree<T>::Iterator::hasNext(){
	return current >= 0;
}

template<typename T>
inline long vEBTree<T>::Iterator::next(){
	long ret = current;
	current = t->nextSetElement(ret+1);
	if(current > size) current = -1;
	return ret;
}

template<typename T>
vEBTree<T>::FilterIterator::FilterIterator(vEBTree<T>* t, OrderedSet<long>* filter){
	this->t = t;
	this->filter = filter;
	word_size = t->word_size;
	size = t->size();
	current = 0;
}

template<typename T>
vEBTree<T>::FilterIterator::~FilterIterator(){}

template<typename T>
inline void vEBTree<T>::FilterIterator::start(){
	//initialize the variables
	current = t->nextSetElement(0);
	while(filter->isInCompl(current) && current < size){
		current = t->nextSetElement(current + 1);
	}
	if(current >= size) current = -1;
}

template<typename T>
inline void vEBTree<T>::FilterIterator::restart(){
	start();
}

template<typename T>
inline void vEBTree<T>::FilterIterator::restartFrom(long i){
	//initialize the variables
	current = t->nextSetElement(i);
	while(filter->isInCompl(current) && current < size){
		current = t->nextSetElement(current + 1);
	}
	if(current >= size) current = -1;
}

template<typename T>
inline bool vEBTree<T>::FilterIterator::hasNext(){
	return current >= 0;
}

template<typename T>
inline long vEBTree<T>::FilterIterator::next(){
	//initialize the variables
	long ret = current;
	current = t->nextSetElement(ret);
	while(filter->isInCompl(current) && current < size){
		current = t->nextSetElement(current + 1);
	}
	if(current >= size) current = -1;
	return ret;
}

template<typename T>
inline bool vEBTree<T>::isEmpty(){
	vEBTree<T>* top = levels[height -1];
	long sz = top->sizeInWord();
	for(long i = 0; i < sz; i++){
		if(top->treeNode(i) != 0) return false;
	}
	return true;
}

template<>
inline void vEBTree<int>::show(){
	printf("Estrutura!!! \n");
	for(int i = 0; i < height; i++){
		printf("vetor no nivel %d : size = %lu \n", i, levels[i]->size());
		for(int j = 0; j < levels[i]->size(); j++){
			if(levels[i]->isInSet(j))printf("(%d)",j);
		}
		printf("\n");
	}
}

template<>
inline void vEBTree<long>::show(){
	printf("Estrutura!!! \n");
	for(int i = 0; i < height; i++){
		printf("vetor no nivel %d : size = %lu \n", i, levels[i]->size());
		for(int j = 0; j < levels[i]->size(); j++){
			if(levels[i]->isInSet(j))printf("(%lu)",j);
		}
		printf("\n");
	}
}

template <typename T>
class vEBTreeFactory :OrderedSetFactory<long>{
public:

	virtual OrderedSet<long>* newOrderedSet(long n) = 0;

	virtual OrderedSet<long>* newOrderedSet(long n, void* handle) = 0;
};

#endif /* VEBTREE_H_ */
